# -*- coding: utf-8 -*-            
# @Time : 2022/12/14 23:20
# @Author  : lining
# @FileName: LRU缓存.py
"""
LRU Least Recently Used,最近最少使用，淘汰旧的
LFU 最近最频繁使用，淘汰使用次数最少的
"""
map_ = {'length' : 0}
class Node():
    def __init__(self,data=None, next_= None, pre = None):
        self.data = data
        self.next_ = next_
        self.pre = pre

    # 添加节点
    def append(self, link_node, node):
        """
        :param link_node: 最后一个节点
        :param node: 新节点
        :return:
        """
        last_node = link_node.next_
        link_node.next_ = node
        node.pre = link_node
        node.next_ = last_node
        last_node.pre = node
        map_[node.data] = node
        map_['length'] = map_['length']+1

    # 删除节点
    def delete(self, node):
        node_next = node.next_
        node_pre = node.pre
        node_pre.next_ = node_next


class LRU():
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next_ = self.tail
        self.tail.pre = self.head
        self.current_node = self.head
        # 长度为5的缓存
        self.len = 5

    def lru(self, data):
        # 在缓存内
        if data in map_:
            node = map_[data]
            node_next = node.next_
            node_pre = node.pre
            node_pre.next_ = node_next
            head = self.head.next_
            self.head.next_ = node
            node.next_ = head
            node.pre = self.head
        else:
            # 已经满了,且不在原链表内，先删除最后一个元素
            if map_['length'] == self.len and data not in map_:
                last_node = self.tail.pre
                last_node_pre = last_node.pre
                last_node_pre.next_ = self.tail
                map_['length'] = map_['length'] - 1
                map_.pop(last_node.data)
                self.current_node = last_node_pre
            new_node = Node(data)
            new_node.append(self.current_node, new_node)
            self.current_node = new_node

    def print_lru(self):
        node = self.head.next_
        while node.data:
            print(node.data)
            node = node.next_

a = LRU()
a.lru(1)
a.lru(2)
a.lru(3)
a.lru(4)
a.lru(5)
a.lru(6)
a.lru(6)
a.print_lru()


